package leetcode;

import java.util.HashSet;
import java.util.Set;

public class UniqueSubstringsInWraparound {

	
	public static void main(String[] args) {
		String string = "abaab";
		UniqueSubstringsInWraparound object = new UniqueSubstringsInWraparound();
		System.out.println(object.findSubstringInWraproundString_2(string));
	}
	
	//找出p的所有字符串不包括重复的
    public int findSubstringInWraproundString(String p) {
        if(p == null || p.length() <= 0){
        	return 0;
        }
    	
    	Set<String> set = new HashSet<>();
    	
    	int length = p.length();
    	
    	//题意理解错了，s是"abcdef...xyz"的无限重复，而不是哪一位都可以为任意值
    	for (int i = 0; i < length; i++) {
    		set.add(p.charAt(i) + "");
    		for (int j = i + 1; j < length; j++) {
    			char cur = p.charAt(j);
    			char pre = p.charAt(j - 1);
    			if(cur == 'a' && pre == 'z' || (cur - pre == 1)){
    				set.add(p.substring(i, j + 1));
    			}else{
    				break;
    			}
			}
		}
    	return set.size();
    }
    
    //想了一下，应该是dp
    public int findSubstringInWraproundString_2(String p) {
        if(p == null || p.length() <= 0){
        	return 0;
        }
    	int[] map = new int[26];
    	
    	int length = p.length();
    	int[][] dp = new int[length][27];
    	//dp[i][j]表示p[0...i]中以字符j结尾的个数
    	//dp[i][26]用来存储总的数据
    	char c = p.charAt(0);
    	dp[0][c - 'a'] = 1;
    	dp[0][26] = 1;
    	map[c - 'a'] = 1;
    	for (int i = 1; i < length; i++) {
    		char cur = p.charAt(i);
    		//还有重复的无法进行判断，比如ababb结果是4，而实际应该是a
    		if(cur == 'a'){
    			dp[i][26] = dp[i - 1][26] + (dp[i][cur - 'a'] = dp[i - 1]['z' - 'a']);
			}else{
				
				dp[i][26] = dp[i - 1][26] + (dp[i][cur - 'a'] = dp[i - 1][cur - 1 - 'a']);
			}
    		if(map[cur - 'a'] == 0){
    			map[cur - 'a'] = 1;
    			dp[i][26]++;
    		}
    		dp[i][cur - 'a']++;
    		System.out.println("cur i : " + i + " " + dp[i][26]);
		}
    	return dp[length - 1][26];
    }
    
    //上面的dp不对,因为可能含有重复的数字
    public int findSubstringInWraproundString_3(String p) {
        if(p == null || p.length() <= 0){
        	return 0;
        }
    	int length = p.length();
    	
    	// store longest contiguous substring ends at current position.
        int maxLengthCur = 0; 
    	int[] dp = new int[26];
    	//dp[i][j]表示p[0...i]中以字符j结尾的个数
    	for (int i = 0; i < length; i++) {
    		//比如zabc,长度为4,那么以c结尾的就是zabc、abc、bc、c
    		if (i > 0 && (p.charAt(i) - p.charAt(i - 1) == 1 || (p.charAt(i - 1) - p.charAt(i) == 25))) {
                maxLengthCur++;
            }else {
                maxLengthCur = 1;
            }
    		int index = p.charAt(i) - 'a';
    		//如果zabc后面遇到yzabc,也通过比较最长的来消除了重复
    		dp[index] = Math.max(dp[index], maxLengthCur);
		}
    	int sum = 0;
    	for(int i = 0; i < dp.length; i++){
    		sum += dp[i];
    	}
    	return sum;
    }
}
